#include <iostream>

using namespace std;

/*
Given a dictionary which contains n strings. Given another single string and 
find the total ways to split the string and make sure all substrings are valid 
string in dictionary.
*/

/// this routine is to simulate the lookup in dictionary
bool FindWordInDictionary(char *string, int start, int end )
{
	char *temp = new char [end-start+2];
	for( int i=0; i<end-start+1; i++ )
	{
		temp[i] = string[start+i];
	}
	temp[end-start+1] = '\0';

	if( strcmp(temp, "I") == 0 ||
	    strcmp(temp, "am") == 0  ||
	    strcmp(temp, "a") == 0  ||
	    strcmp(temp, "cool") == 0  ||
	    strcmp(temp, "boy") == 0  ||
	    strcmp(temp, "Iam") == 0  ||
	    strcmp(temp, "acool") == 0  ||
	    strcmp(temp, "coolboy") == 0 )
	{
		delete [] temp;
		return true;
	}
	delete [] temp;
	return false;
}

int SplitCount( char *string, int start, int end )
{
	if( !string || start > end )
		return 0;
	int count = 0;
	if( FindWordInDictionary( string, start, end) )
		count++;
	for( int i = start; i< end; i++ )
	{
		if( FindWordInDictionary( string, start, i) )
		{
			count += SplitCount( string, i+1, end );
		}
	}
	return count;
}

int main()
{
	char *string = "Iamacoolboy";
	cout<<"the count to split string "<<string<<" is "<<SplitCount( string, 0, strlen(string) )<<endl;

	cout<<"Press any key to terminate..."<<endl;
	return getchar();
}